package dynamicStudy;

public class UpdateMatrix {

    /**
     * LeetCode T542 01矩阵
     * 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
     *
     * 两个相邻元素间的距离为 1 。
     * @param args
     */
    public static void main(String[] args) {

    }

    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        //定义状态方程
        int[][] dp = new int[m][n]; //初始化均为0

        //初始化第一个元素
        dp[0][0] = Integer.MAX_VALUE;
        if (mat[0][0] == 0){
            dp[0][0] = 0;
        }
        //上、左方向
        for (int j = 1; j < n; j++){
            if (mat[0][j] == 0){
                dp[0][j] = 0;
            } else {
                dp[0][j] = dp[0][j - 1] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[0][j - 1] + 1;
            }
        }
        for (int i = 1; i < m; i++){
            if (mat[i][0] == 0){
                dp[i][0] = 0;
            } else {
                dp[i][0] = dp[i - 1][0] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i - 1][0] + 1;
            }
            for (int j = 1; j < n; j++){
                if (mat[i][j] == 0){
                    dp[i][j] = 0;
                } else {
                    int min = Math.min(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = min == Integer.MAX_VALUE?Integer.MAX_VALUE:min+1;
                }
            }
        }
        //下、右方向
        for (int j = n - 2; j >= 0; j--){
            dp[m - 1][j] = Math.min(dp[m - 1][j], dp[m - 1][j + 1] + 1);
        }
        for (int i = m - 2; i >= 0; i--){
            for (int j = n - 1; j >= 0; j--){
                if (j==n-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
                } else {
                    dp[i][j] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j+ 1])+1);
                }
            }
        }
        return dp;
    }
}
